Day-7 Divide-and-Conquer-2 : 求解遞迴式

2021 iThome 鐵人賽

DAY 7

自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列第 7 篇

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-09-18 15:30:32

4413 瀏覽

分享至

如何求解遞迴式

目前主要有三種方法來求解遞迴式(至今沒有任何一個好的演算法可以有效地解決遞迴式)

代換法(substitution method)

他主要遵循以下三種想法

猜大概的答案，例如猜測演算法大約為 ${cn}^2$
我們要試著解出常數c，我們會試著驗證這個遞迴式是否成立，使用數學歸納法進行驗證。
找到常數，使問題或是我們的想法可以成立。

Example 1. $T(n)=4T(n/2) + n$ , $T(1)=$ Θ $(1)$
我們先猜測大約 $T(n) = O(n^3)$
先證明基本情況， $T(1) =$ Θ $(1)$ $<= {c_1}^3$ ，當c足夠大時，不等式成立。
接下來證明 $T(n)$ 最多達到 ${cn}^3$ ，我們將這個表示式展開， $T(k)<={ck}^3$ 對 $k <= n$ 成立，這裡不使用Big-O符號作為表示原因在於不能對Big-O符號進行歸納，以下面例子來說:

假設 $n = O(1)$ ，當n足夠大時，n會小於等於常數1，也就是n不會超出常數時間。如果這個為真，那任何演算法都將會是常數時間複雜度，但顯然這是錯的
基本情況 $1 = O(1)$
根據數學歸納法，如果假設 $n - 1 = O(1)$
我們可以推出 $n = (n - 1) + 1$ ，如果 $n - 1$ 是 $O(1)$ ，1也是 $O(1)$
則總和還是 $O(1)$ ，因此由數學歸納法， $n = O(1)$ 正確

但這是一個錯誤的證明，問題點是我們忽略了常數的變化 $O(1) + O(1)$ 可能會使常數加倍，如果是有限情況下，常數不斷加倍仍然是常數，但如果這是一個無窮表示式，常數乘了n倍，那就會出問題了，常數會根據n變化，因此不能被忽略。

為了避免上面這個問題，於是我們將常數寫出來，以k做為表示， $T(k)<={ck}^3$ 對 $k < n$ 成立，我們將 $T(n)$ 展開， $https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n$ ，根據我們上面的歸納假設
$https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E3%20%2B%20n$
$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cfrac%7B1%7D%7B2%7Dcn%5E3%2Bn$
$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20cn%5E3%20-%20(%5Cfrac%7B1%7D%7B2%7Dcn%5E3-n)$ (小括弧部分為剩餘項，是為了化簡到 $cn^3$ )
$<= cn^3$ , 當餘項大於或是等於零時

我們證明一下餘項必定大於或等於零，如果c為2，則 $n^3 - n$ 必定大於零成立，如果c為1，則 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B2%7Dn%5E3%20-%20n$ ，當n大於1點多時，必成立。

到這裡我們證明完畢 $T(n)$ 小於或等於一個常數乘上 $n^3$ ，這個就是 $T(n)$ 的上界，但其實這不是一個嚴格的上界，因為 $n^2$ 也同樣會成立。這裡所證明的不是 $T(n)$ 的答案就是 $n^3$ ，而是 $T(n)$ 不會超過 $n^3$ 這件事情。

我們試著證明 $T(n) = O(n^2)$
$T(k)<={ck}^2$ 當 $k < n$
$https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n$ ，使用上面歸納法的假設將 $https://chart.googleapis.com/chart?cht=tx&chl=T(%5Cfrac%7Bn%7D%7B2%7D)$ 展開
$https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E2%20%2B%20n$
${cn}^2+n$
${cn}^2+(n)$ ，(小括號的部分式為餘項)
${cn}^2-(-n)$ ，我們必須讓餘項非負，因為對於遞迴式來說，只討論大於等於1的情況
寫到這裡我們會發現我們無法完成這個歸納法，因此，我們需要修改我們假設
假設 $T(k) <= {c_1}k^2-{c_2}k$ 當 $k < n$ ，這裡我們改進了我們的歸納法假設，我們之前用的假設是與目前相比較弱的假設，在現在這個假設中，我們把低次項加入進來考慮，先前的假設忽略了常數項與低次項。

我們這裡之所以考慮進來低次項，原因是我們期望在解遞迴式的過程，可以把n給消除掉，只留下 ${cn}^2$ ，下面開始證明

$https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n$
假設 $T(k) <= {c_1}k^2-{c_2}k$ 當 $k < n$
$https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204%5Bc_1(%5Cfrac%7Bn%7D%7B2%7D)%5E2-c_2(%5Cfrac%7Bn%7D%7B2%7D)%5D%20%2B%20n$
$c_1n^2+(1-2c_2)n$ ，這裡使用了更強的歸納假設，因此需要留下最次低項
$c_1n^2-c_2n - [(-1+c_2)n]$ 中括號部分為餘項，同時我們希望餘項非負
我們發現當 $c_2 >= 1$ 時，餘項恆正，因此證明
$T(n) <= c_1n^2-c_2n$ ，當 $c_2 >= 1$ 時

接著回頭看到基本情況的部分
$T(1) <= c_11^2-c_2, T(1) =$ Θ $(1)$
我們會發現到， $c_2$ 需要大於等於1，那 $c_1$ 需要足夠大，才能滿足 $T(1) =$ Θ $(1)$ ，因此整個歸納法的精確結論如下
$T(n) <= c_1n^2-c_2n$ ，當 $c_2 >= 1$ 且 $c_1$ 相對於 $c_2$ 足夠大時

遞迴樹法(recursion-tree method)

遞迴樹解法，顧名思義是把遞迴以樹的形式展開，雖然直覺，但是相較於代換法沒有那麼的嚴謹，中間遞迴過程有時候會以...省略，這裡需要特別注意，若要求嚴謹，可以使用代換法去驗證遞迴樹，但一般來說不會那麼做。

Example 1. $T(n) = T(n/4) + T(n/2) + n^2$
首先，我們先將這個遞迴式以樹的形式表達，如下圖

再將 $T(n/4)$ 和 $T(n/2)$ 帶入 $T(n)$ ，也就是遞迴展開的概念。

然後一直不斷下去，直到最後，我們會得到一堆葉節點，為Θ $(1)$ 。

這裡我們可以注意到一件事情，左子樹和右子樹的遞迴展開速度是不一樣的，會導致兩子樹的高度不同，我們會難以計算葉子的數量，但我們能夠確定一件事情，就是葉子的數量一定會少於n，一開始問題的規模為n，每一次遞迴會減少1/4，因此當遞迴結束於，葉的數量必定會少於n，我們試著把這個樹每一層的結果加總

我們會發現每一層都會相差 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B5%7D%7B16%7D$ ，我們把加總，也就是求這個等比級數的何
$https://chart.googleapis.com/chart?cht=tx&chl=(1%20%2B%20%5Cfrac%7B5%7D%7B16%7D%20%2B%20%5Cfrac%7B25%7D%7B256%7D%20%2B%20...%20%2B%20%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D%2B...)n%5E2$
$https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bi%3D0%7D%5Ek%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D$
我們知道上面這個公式計算之後，我們會得到某個常數，我們以c為代表，整個等比級數的何為
$cn^2$ ，且 $cn^2<2n^2$ ，以Ω $(n^2)$ 表示
而這個方法不嚴謹的地方在於等比級數得假設，我們只驗證了前三項就認定他是等比級數。下面會介紹基於遞迴樹的更嚴謹的方法，稱為主定理(master theorem)。

主定理(master theorem)

主定理有一個限制，那就是只能使用到特定的遞迴式上面，這些遞迴式需要符合 $T(n)=aT(n/b)+f(n)$ 這樣的形式，有a個相同的子問題，每個子問題的規模皆相同，不同於上一個例題，有兩個不同規模的子問題。

還有一些限制條件，a需要大於或是等於1，也就是至少要遞迴一次，b需要嚴格大於1，因為我們必須讓子問題的規模越來越小，f(n)需要趨近於正(asymptotically positive)，也就是當n足夠大時， $f(n)$ 必須為正，以數學式表示，即為存在某一個點 $n_0$ ，當 $n>=n_0$ 時， $f(n) > 0$

主定理是基於將非遞迴函數 $f(n)$ 和 $n^{logb^a}$ 進行比較，而比較的過程，會出現三種情況，分別為大於，等於，小於，我們可能會直觀的想到使用little-o，big-Θ，和smail-ω做為表示，但是，中間會存在一些灰色地帶，是我們無法用這些符號進行表示的。

第一種情況，對於ε $>0$ 的情況
有 $f(n) = O(n^{logb^a-\varepsilon})$ ，則
$T(n) = \Theta(n^{logb^a})$
第二種情況，對於ε $>=0$
有 $T(n) = \Theta(n^{logb^a}lg^{\varepsilon+1}n)$ ，則
$T(n) = \Theta(n^{logb^a}lg^{\varepsilon+1}n)$
第三種情況，對於ε $>0$ 的情況，且需要確保 $f(n)$ 在遞迴時不斷地變小
有 $f(n) = \Omega(n^{logb^{a+\varepsilon}})$ 且對某個常數 $c<1$ 和足夠大的n，有 $https://chart.googleapis.com/chart?cht=tx&chl=af(%5Cfrac%7Bn%7D%7Bb%7D)%3C%3Dcf(n)$ ，則
$T(n) = \Theta(f(n))$

Example 1. $https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn$
首先，先確認是否符合主定理的限制， $T(n)=aT(n/b)+f(n)$
發現符合限制，找到 $a = 4, b = 2$ ，先確認 $T(n)$ 是屬於哪一種情況，也就是先計算 $n^{log}b^a$
$n^{log}b^a$ ，將 $a = 4, b = 2$ 代入，得到
$n^{log}2^4 = n^2$
我們比較 $f(n)$ 和 $n^{log}b^a$ ，發現 $n^{log}b^a>f(n)$ ，也就是 $f(n) = O(n^{2-\varepsilon})$ ，因此屬於第一種情況，則結果為 $T(n) = \Theta(n^{log_b^a})$ ，也就是 $T(n) = \Theta(n^2)$

Example 2. $https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E2$
首先，先確認是否符合主定理的限制， $T(n)=aT(n/b)+f(n)$
發現符合限制，找到 $a = 4, b = 2$ ，先確認 $T(n)$ 是屬於哪一種情況，也就是先計算 $n^{log}b^a$
$n^{log}b^a$ ，將 $a = 4, b = 2$ 代入，得到
$n^{log}2^4 = n^2$
我們比較 $f(n)$ 和 $n^{log}b^a$ ，發現 $n^{log}b^a>=f(n)$ ，也就是 $f(n) = \Theta(n^{logb^a}lg^\varepsilon n)$ ，因此屬於第二種情況，則結果為 $T(n) = \Theta(n^{logb^a}lg^{\varepsilon +1}n)$ ，也就是 $T(n) = \Theta(n^{2}lgn)$

Example 3. $https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E3$
首先，先確認是否符合主定理的限制， $T(n)=aT(n/b)+f(n)$
發現符合限制，找到 $a = 4, b = 2$ ，先確認 $T(n)$ 是屬於哪一種情況，也就是先計算 $n^{log}b^a$
$n^{log}b^a$ ，將 $a = 4, b = 2$ 代入，得到
$n^{log}2^4 = n^2$
我們比較 $f(n)$ 和 $n^{log}b^a$ ，發現 $n^{log}b^a<f(n)$ ，也就是 $f(n) = \Omega(n^{logb^{a+\varepsilon}})$ ，因此屬於第三種情況，則結果為 $T(n) = \Theta(f(n))$ ，也就是 $T(n) = \Theta(n^{3})$